package binTree;

import java.util.Scanner;

/**
 *编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。
 * 例如如下的先序遍历字符串：
 * ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
 */
public class NowCoder_BuildTree {
    private static class TreeNode {
        char val;
        TreeNode left;
        TreeNode right;

        TreeNode() {

        }

        TreeNode(char val) {
            this.val = val;
        }

        public TreeNode(char val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    //index表示处理到哪个字符了
    private static int index=0;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        //多行输入
        while (scanner.hasNext()){
            //每次读取一行前序遍历的结果
            String str = scanner.next();
            //根据前序遍历二叉树
            TreeNode root = preOrderBuild(str);
            //中序遍历输出
            inOrder(root);
            //换行
            System.out.println();
            index=0;

        }




    }
    //中序遍历

    private static void inOrder(TreeNode root) {
        if (root==null){
            return;
        }
        inOrder(root.left);
        System.out.println(root.val+" ");
        inOrder(root.right);

    }

    private static TreeNode preOrderBuild(String str) {
        char cur = str.charAt(index);
        if (cur=='#'){
            return null;
        }
        TreeNode root = new TreeNode(cur);
        index++;
        root.left=preOrderBuild(str);
        index++;
        root.right=preOrderBuild(str);
        return root;






    }


}
